package kg.aibek.projecteuler.p10;

import java.util.Arrays;

public class Problem14 {
	private final int MAX = 1000000;
	private int[] n = new int[MAX];

	private int count(long number) {
		if (number < MAX) {
			int nn = (int) number;
			if (n[nn] == -1) {
				if (number % 2 == 0) {
					n[nn] = count(number / 2) + 1;
				} else {
					if (number * 3 + 1 < 0) {
						System.out.println("Bingo");
					}
					n[nn] = count(number * 3 + 1) + 1;
				}
			}
			return n[nn];
		} else {
			if (number % 2 == 0) {
				return count(number / 2) + 1;
			} else {
				return count(number * 3 + 1) + 1;
			}
		}
	}

	public void solve() {
		Arrays.fill(n, -1);
		n[1] = 1;
		n[2] = 2;
		n[3] = 7;
		n[4] = 3;

		int count = 0;
		int number = 0;
		for (int i = 1; i < MAX; i++) {
			int cc = count(i);
			if (cc >= count) {
				count = cc;
				number = i;
			}
		}
		System.out.println(number);
	}

	public static void main(String[] args) {
		long time = System.nanoTime();
		Problem14 p = new Problem14();
		p.solve();
		time = System.nanoTime() - time;
		System.out.println("Time took = " + time * 1.0e-9);
	}
}
